The present invention relates to a key update system, a key management device, a communication terminal, and a key information construction method for a multihop network. In particular, the present invention relates to a technology that safely updates a key such that a communication terminal of a third party that is not part of the network or a communication terminal that needs to be removed from the network cannot identify the key after it has been updated. In addition, the present invention relates to a technology that safely updates a key such that a communication terminal that newly joins the network cannot identify a key that was previously used.
A multihop network is a network in which one or a plurality of communication terminals relay data communication between any given two communication terminals. The communication system may be wired or wireless.
FIG. 1 shows the normal structure of a multihop network system. The multihop network system includes an authentication management device 100 and a plurality of transmission terminals 110 that are members of the network. The transmission terminals 110 share a network common key K0. In this multihop network, when one of the transmission terminals 110 is removed from the network, or when a new transmission terminal 110 joins the network, the network common key K0 has to be updated to a new common key K0′ without the transmission terminals 110 recognizing.
One way of achieving the above objective is to adopt a method using a Logical Key Hierarchy (LKH) key distribution protocol, such as that proposed in Adrian Perrig and J. D. Tygar's “Secure Broadcast Communication in Wired and Wireless Networks”, pp. 120-123, Translation Supervisor Mizoguchi Fumio, Kyoritsu Shuppan Co., Ltd. FIG. 21 provides a simple explanation of a LKH key distribution protocol. Hereinafter, key information that has a hierarchical structure associated with a tree structure, which is one type of hierarchical structure, will be referred to as a “key tree”. In the LKH key distribution protocol, in order to perform efficient key update, an authentication management device manages the key tree. Each node in the key tree (K0, K1, K2, K3, K4, K5, K6) respectively represents an encryption key for distributing a key. The authentication management device assigns each communication terminal to a leaf of the key tree (meaning a leaf in the tree structure). At this time, each communication terminal learns all of the keys from its own leaf node to the root of the key tree. However, the communication terminal does not learn anything about the other keys in the key tree. The key K0 that is located at the tree root is the network common key that is shared by all of the communication terminals.
Note that, in the case that a communication terminal D1 that is a member of the network needs to be removed from the network, the authentication management device updates, amongst the encryption keys of the key tree that it manages, the keys K0, K1 and K3 that the communication terminal D1 holds. The keys are respectively updated to K0′, K1′ and K3′. In addition, in order to respectively update the keys K0, K1 that each communication terminal holds to K0′, K1′, the authentication management device broadcasts the following key update message in which E (X, Y) expresses the meaning that key X is used to encrypt message Y.
E (K4, K1′), E (K1′, K0′), E (K2, K0′)
Since a communication terminal D2 knows the key K4, the communication terminal D2 can obtain K1′ from the key update message. Next, the communication terminal D2 can use the key K1′ obtained from the key update message to obtain the new network common key K0′. Further, since the communication terminals D3 and D4 know the key K2, the communication terminals D3 and D4 can obtain the new network common key K0′ from the key update message.
On the other hand, the communication terminal D1 does not hold any of the keys needed to decrypt the key update message. Accordingly, the communication terminal D1 is not able to obtain the new key. Thus, as described above, with the LKH key distribution protocol it is possible to efficiently notify all communication terminals, with the exception of the communication terminal D1 that needs to be removed from the network, of the new network common key K0′.
However, the above-described LKH key distribution protocol was not devised with a multihop network system in mind. Since a multihop network system uses a communication system in which one or more terminals act as relays, the communication load related to delivering the key update message will be different for each communication terminal. Up to now, no efficient method has been developed for performing key update as described above using the unique characteristics of a multihop network.